Recent advances in cell phones and mobile technology provide opportunities for new and improved services to the end user. One set of these services is referred to as Location-Based Services (LBS), which is provided based on contextual information from a user's or object's geographic location. These services can vary from navigation applications and location-based emergency alerts, such as traffic accident or hurricane evacuation notifications, to friend finders that alert users when they are in close proximity to a friend. They are often associated with Global Positioning Systems (GPS)-enabled cell phones, but other devices such as telemetry units or wireless sensors may also be part of an LBS system.
LBS are based on various positioning technologies, including assisted GPS, cellular network triangulation or trilateration, or a hybrid of these and other methods. These technologies all rely on wireless communications, and, therefore, there is an inherent amount of uncertainty when determining a user's position in real-time. This uncertainty grows as positioning technologies are disrupted, such as when a GPS-enabled cell phone goes indoors, into a tunnel, in a vehicle, in an urban canyon, or is otherwise shielded or prevented from obtaining a location fix. This disruption may also be accompanied by a disruption in communication technology that the device uses to communicate with a server. In these circumstances, the real-time position of the cell phone is unknown.
When the knowledge of the geographic position is lost, certain techniques can be performed that provide an estimate of where the device is currently located. This is commonly referred to as dead-reckoning, and is most common in devices that utilize technology such as accelerometers in addition to a positioning technology, such as GPS. GPS provides the overall knowledge of where the device is located, but accelerometers may be used when GPS is lost by measuring small changes in the device's acceleration and, therefore, computing a new estimated location as a distance from the last known location. Accelerometers are also used for power conservation because they utilize much less power than a GPS system. In order to save power, a device may lie dormant and observe only its accelerometers. When acceleration is detected (which implies movement), the GPS system is turned on and attempts to determine the device's location. This saves power over continuously polling the GPS for a location when the device is sitting still. However, certain resource-constrained mobile devices, such as cell phones, may not have built-in accelerometers, or they may not be accessible to software applications running on the phone or server-side components. In these situations, a new method is needed to accurately estimate a device's location to provide reliable and transparent LBS to end-users of a mobile device based on immediate, recent, and/or archived data.